package leetcode

func solveSudoku(board [][]byte) {
	var line, column [10][10]bool
	var block [3][3][10]bool
	//记录空白的地方的坐标值
	var spaces [][2]int

	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] == '.' {
				spaces = append(spaces, [2]int{i, j})
			} else {
				temp := board[i][j] - '0'
				line[i][temp] = true
				column[j][temp] = true
				block[i/3][j/3][temp] = true
			}
		}
	}
	var dfs func(int) bool
	//递归
	dfs = func(pos int) bool {
		//如果填满了就返回true
		if pos == len(spaces) {
			return true
		}
		i, j := spaces[pos][0], spaces[pos][1]
		for digit := byte(1); digit <= 9; digit++ {
			if !line[i][digit] && !column[j][digit] && !block[i/3][j/3][digit] {
				line[i][digit] = true
				column[j][digit] = true
				block[i/3][j/3][digit] = true
				board[i][j] = digit + '0'
				if dfs(pos + 1) {
					return true
				}
				line[i][digit] = false
				column[j][digit] = false
				block[i/3][j/3][digit] = false
			}
		}
		return false
	}
	dfs(0)
}
//36. 有效的数独
func isValidSudoku(board [][]byte) bool {
	var line, column [10][10]bool
	var block [3][3][10]bool

	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				temp := board[i][j] - '0'
				if line[i][temp] || column[j][temp] || block[i/3][j/3][temp] {
					return false
				}
				line[i][temp] = true
				column[j][temp] = true
				block[i/3][j/3][temp] = true
			}
		}
	}
	return true
}
